package com.singzi.leetcode.jianzhiOffer;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Stack;

public class T0031 {
    public static void main(String[] args) {
        int[] pushed = {2,1,3,0};
        int[] popped = {1,3,0,2};
        Solution0031 solution0031 = new Solution0031();
        System.out.println(solution0031.validateStackSequences(pushed, popped));
    }
}
class Solution0031 {
    public boolean validateStackSequences(int[] pushed, int[] popped) {

        HashMap<Integer, Integer> map = new LinkedHashMap<>();
        Stack<Integer> st = new Stack<>();
        int maxIndex = 0;
        int n = popped.length;
        if(n == 0 || n == 1) return true;
        for(int i = 0;i < n;i++){
            map.put(pushed[i], i);
        }
        for(int i = 0;i < map.get(popped[0]);i++){
            st.push(i);
        }
        if(!st.isEmpty()) maxIndex = st.peek() + 1;
        else maxIndex = 1;
        for(int i = 1;i < popped.length;i++){
            if(!st.isEmpty()&& map.get(popped[i]) < st.peek()) return false;
            else if(!st.isEmpty() && map.get(popped[i]) == st.peek()){
                st.pop();
            }
            else{
                maxIndex = map.get(pushed[i]) + 1;
                for(int j = maxIndex + 1;j < map.get(popped[i]);j++){
                    st.push(map.get(pushed[j]));
                }

            }
        }
        return true;
    }
}